const w = [1, 2, 3];
const v = [6, 10, 12];
const C = 5;

/**
 * @description: 动态规划背包问题
 * @param {[Number]} w
 * @param {[Number]} v
 * @param {Number} C
 * @return {Number}
 */
function package01_dp(w, v, C) {
  const size = w.length;
  const dp = new Array(size).fill(0).map((v) => new Array(C + 1).fill(-1));

  for (let i = 0; i <= C; i++) {
    dp[0][i] = i >= w[0] ? v[0] : 0;
  }

  for (let i = 1; i < size; i++) {
    for (let j = 0; j <= C; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= w[i]) {
        dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
      }
    }
  }

  return dp[size - 1][C];
}

/**
 * @description: 动态规划,优化空间复杂度为O(C)
 * @param {[Number]} w
 * @param {[Number]} v
 * @param {Number} C
 * @return {Number}
 */
function package01_dp_optimize(w, v, C) {
  const size = w.length;
  const dp = new Array(2).fill(0).map((v) => new Array(C + 1).fill(-1));

  for (let i = 0; i <= C; i++) {
    dp[0][i] = i >= w[0] ? v[0] : 0;
  }

  for (let i = 1; i < size; i++) {
    for (let j = 0; j <= C; j++) {
      dp[i % 2][j] = dp[(i - 1) % 2][j];
      if (j >= w[i]) {
        dp[i % 2][j] = Math.max(dp[i % 2][j], v[i] + dp[(i - 1) % 2][j - w[i]]);
      }
    }
  }

  return dp[(size - 1) % 2][C];
}

/**
 * @description: 记忆化搜索
 * @param {[Number]} w
 * @param {[Number]} v
 * @param {Number} C
 * @return {Number}
 */
function package01_memo(w, v, C) {
  const size = w.length;
  const memo = new Array(size).fill(0).map((v) => new Array(C + 1).fill(-1));

  return bestValue(w, v, C, size - 1);

  function bestValue(w, v, c, index) {
    if (index < 0 || c <= 0) {
      return 0;
    }

    if (memo[index][c] !== -1) {
      return memo[index][c];
    }

    let result = bestValue(w, v, c, index - 1);

    if (c >= w[index]) {
      result = Math.max(
        result,
        v[index] + bestValue(w, v, c - w[index], index - 1)
      );
    }

    memo[index][c] = result;

    return result;
  }
}

/**
 * 测试
 */
console.time();
console.log('package01_dp:', package01_dp(w, v, C));
console.timeEnd();
console.time();
console.log('package01_dp_optimize:', package01_dp_optimize(w, v, C));
console.timeEnd();
console.time();
console.log('package01_memo:', package01_memo(w, v, C));
console.timeEnd();
